import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 08 - 27
 * Time: 12:14
 */
//牛客 二叉树的中序遍历
public class
Solution4 {
    //法一 官方推荐方法
    public List<Integer> inorder(TreeNode root){
        List<Integer> list = new ArrayList<>();//递归有返回值时，顺序表定义在这个递归函数的里面。递归没有返回值时，顺序表定义在这个递归函数的外面
        if(root == null) return list;
        List<Integer> list1 = inorder(root.left);
        list.addAll(list1);
        list.add(root.val);
        List<Integer> list2 = inorder(root.right);
        list.addAll(list2);
        return list;
    }
    public int[] inorderTraversal (TreeNode root) {
        List<Integer> list = inorder(root);
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    //法二 官方方法
    public int[] inorderTraversal1 (TreeNode root) {
        if(root == null) return new int[0];
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {//条件是root!=null||!stack.isEmpty()
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }
}
